COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00006 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a11.tex[106,phy] \today\hfill}

\bigskip
\ctrline{\bf Back-of-the-Envelope Calculation Number 18736}

\bigskip
The Pluto lander spacecraft needs to locate the largest unobstructed
area in an image which has been stored as a $1000\times 1000$ array.
Calling $N$ ($=1000$) the width and height of the array, the program
will surely need to go through its inmost iteration at least $N↑2$~times
even to inspect the whole image. What is the largest power of $N$
that might be acceptable as the number of times the program executes
the inmost iteration? The answer determines the programmer's aspiration
level.

Let's say the majority of operations in the computer, like add, fetch,
and store, take about ten nanoseconds $=10↑{-8}$ seconds, and a typical
inmost iteration is about ten operations $=10↑{-7}$ seconds.

For $N↑2$ executions, the time needed is $10↑{-7}\times 1000↑2=0.1$
seconds. For~$N↑3$, $10↑{-7}\times 1000↑3=10↑2$ seconds, about a~minute,
give or take a factor of two. For $N↑4$, $10↑{-7}\times 1000↑4=10↑5$
seconds $=$ one day. For $N↑5$, $10↑{-7}\times 1000↑5=10↑8$
seconds $=$ three years.

Let's guess a speed for the spacecraft around its escape velocity from
the earth, 24000 miles per hour. The computation can not begin until
obstacles about the size of the spacecraft (say 10~feet) are visible.
Using a one-foot diameter lens, and light of wavelength 
$5000 A=2\times 10↑{-5}$ inches, the lens size is about $5\times 10↑5$
wavelengths, and obstacle will be invisible at distances beyond
$10\times (5\times 10↑5)=5\times 10↑6$ feet $=1000$ miles, or two minutes
before impact.

Obviously $N↑4$ executions would be hopeless, $N↑2$ would be easy, and
$N↑3$ is pushing optical technology to its limits. If the estimates
on which the calculation is based are each off by a factor of two
or~so, the conclusion stays the same; the programmer should try for~$N↑2$,
with $N↑3$ as a fallback position. As programmer, I~should then ask
myself how to pass over the image once or twice to come away with the
size and location of the largest unobstructed area.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft July 18, 1984

\bye